#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/3/2 9:33
# ===========================================
#       题目名称： 31. 下一个排列
#       题目地址： https://leetcode.cn/problems/next-permutation/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================

import itertools as it
import copy


class Solution:

    def nextPermutation(self, nums):
        """
            Do not return anything, modify nums in-place instead.
            整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
            例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
            整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
        那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列
        （即，其元素按升序排列）。
            例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
            类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
            而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
            给你一个整数数组 nums ，找出 nums 的下一个排列。
            123456      ->
            123465      ->  6 > 5  change
            123546      ->  5 < 6  index ++ 直至找到小于5的那一位
            ...
            654321

        import itertools as it
        # https://cloud.tencent.com/developer/article/1650456
        # 使用两个序列进行排列组合
        for e in it.product('AB', 'CD'):
            print(''.join(e), end=', ') # AC, AD, BC, BD,
        print('\n---------')
        # 使用一个序列、重复2次进行全排列
        for e in it.product('AB', repeat=2):
            print(''.join(e), end=', ') # AA, AB, BA, BB,
        print('\n---------')
        # 从序列中取2个元素进行排列
        for e in it.permutations('ABCD', 2):
            print(''.join(e), end=', ') # AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC,
        print('\n---------')
        # 从序列中取2个元素进行组合、元素不允许重复
        for e in it.combinations('ABCD', 2):
            print(''.join(e), end=', ') # AB, AC, AD, BC, BD, CD,
        print('\n---------')
        # 从序列中取2个元素进行组合、元素允许重复
        for e in it.combinations_with_replacement('ABCD', 2):
            print(''.join(e), end=', ') # AA, AB, AC, AD, BB, BC, BD, CC, CD, DD,
        """
        # 1. 判断是否是最大的数
        max_nums = list(nums)
        max_nums.sort(reverse=True)
        if nums == max_nums:
            # 默认从小到大排序
            nums.sort()
        else:
            cur_len = 2  # 当前定义的长度
            is_find = False  # 是否找到
            while cur_len <= len(nums) and not is_find:
                cur_nums = tuple(copy.deepcopy(nums[len(nums) - cur_len:]))

                # 序列中取2个元素进行排列 找出比当前这几个大的 进行替换
                small_dict = {}
                for tmp_tup in it.permutations(nums[len(nums) - cur_len:], cur_len):
                    tmp_nums = copy.deepcopy(tmp_tup)
                    # 比较 cur_nums 和 tmp_nums
                    if cur_nums < tmp_nums:
                        small_dict[tmp_nums] = tmp_tup
                if small_dict:
                    is_find = True
                    tmp_list = list(small_dict[sorted(small_dict.keys())[0]])
                    for index in range(len(nums) - cur_len, len(nums)):
                        nums[index] = tmp_list[0]
                        tmp_list.pop(0)
                cur_len += 1
        print(nums)

    def nextPermutation4(self, nums):
        """
            算法有问题
            Do not return anything, modify nums in-place instead.
            整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
            例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
            整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
        那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列
        （即，其元素按升序排列）。
            例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
            类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
            而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
            给你一个整数数组 nums ，找出 nums 的下一个排列。
            123456      ->
            123465      ->  6 > 5  change
            123546      ->  5 < 6  index ++ 直至找到小于5的那一位
            ...
            654321


        """
        next_ind, last_ind = len(nums) - 2, len(nums) - 1  # 扫描开始的下标 最后的下标
        cur_num, cur_ind = nums[last_ind], last_ind
        while cur_ind >= 0:
            if cur_num > nums[next_ind]:
                nums[cur_ind], nums[next_ind] = nums[next_ind], nums[cur_ind]
                break
            else:
                if next_ind - 1 < 0:
                    cur_ind -= 1
                    cur_num = nums[cur_ind]
                    next_ind = cur_num - 1
                else:
                    next_ind -= 1
        print(nums)

    def nextPermutation3(self, nums):
        """
            超出时限 、、、、、、
            Do not return anything, modify nums in-place instead.
            整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
            例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
            整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
        那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列
        （即，其元素按升序排列）。
            例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
            类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
            而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
            给你一个整数数组 nums ，找出 nums 的下一个排列。
            123456
            123465
            123546
            ...
            654321
            123 132 213 231 312 321 123
        """
        # 1. 累加 判断是否相等
        # 最大值 最小值
        maxNums = copy.deepcopy(nums)
        maxNums.sort(reverse=True)
        minNums = copy.deepcopy(nums)
        minNums.sort()
        if maxNums == nums:
            for i in range(len(nums)):  # 保证地址一致
                nums[i] = minNums[i]
            # nums = minNums
        else:
            # 基于原有值累加 找到符合条件的 小于最大值
            currentValue, maxValue = "", ""
            for i in nums:
                currentValue += str(i)
            for i in maxNums:
                maxValue += str(i)
            currentValue, maxValue = int(currentValue), int(maxValue)
            while currentValue < maxValue:
                currentValue += 1
                currentNums = [int(x) for x in str(currentValue)]
                tmpCurrentNums = copy.deepcopy(currentNums)
                currentNums.sort()
                if currentNums == minNums:
                    for i in range(len(nums)):  # 保证地址一致
                        nums[i] = tmpCurrentNums[i]
                    # nums = tmpCurrentNums
                    break
        print(nums)

    def nextPermutation2(self, nums):
        """
            解答错误
            Do not return anything, modify nums in-place instead.
            整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
            例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
            整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
        那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列
        （即，其元素按升序排列）。
            例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
            类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
            而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
            给你一个整数数组 nums ，找出 nums 的下一个排列。
            123456
            123465
            123546
            ...
            654321
            123 132 213 231 312 321 123
        """
        # 1. 累加 判断是否相等
        tmpNumsMax = copy.deepcopy(nums)

        tmpNumsMin = copy.deepcopy(nums)
        # 最大值
        tmpNumsMax.sort(reverse=True)
        # 最小值
        tmpNumsMin.sort()

        if tmpNumsMax == nums:
            nums = tmpNumsMin
        else:
            # 判断前两位是否是有序的  如果有序则进一位 无序则 sort一下
            p = len(nums) - 2
            while p >= 0:
                tmpNums = nums[p:]
                tmpNums.sort(reverse=True)
                if tmpNums == nums[p:]:
                    p -= 1
                else:
                    nums = nums[:p]
                    nums.extend(tmpNums)
                    break
        print(nums)


if __name__ == "__main__":
    s = Solution()
    s.nextPermutation(nums=[1, 2])  # [2,1]
    s.nextPermutation(nums=[1, 2, 3])  # [1,3,2]
    s.nextPermutation(nums=[3, 2, 1])  # [1,2,3]
    s.nextPermutation(nums=[1, 1, 5])  # [1,5,1]
    s.nextPermutation(nums=[1, 2, 3, 4, 5, 6])  # [1, 2, 3, 4, 6, 5]
    s.nextPermutation(nums=[1, 2, 3, 4, 6, 5])  # [1, 2, 3, 5, 4, 6]
    s.nextPermutation(nums=[2, 2, 7, 5, 4, 3, 2, 2, 1])  # [2, 3, 1, 2, 2, 2, 4, 5, 7]
    s.nextPermutation(
        nums=[1, 20, 26, 1, 15, 29, 4, 29, 10, 9, 21, 7, 27, 11, 21, 5, 9, 7, 27, 16, 17, 3, 6, 5, 16, 23, 29, 14, 28,
              21, 2, 29, 3, 29, 0, 18, 28, 5, 10, 9, 6, 23, 8, 25, 26, 21, 1, 5, 29, 28, 14, 8, 1, 20, 13,
              10])  # [1,20,26,1,15,29,4,29,10,9,21,7,27,11,21,5,9,7,27,16,17,3,6,5,16,23,29,14,28,21,2,29,3,29,0,18,
    # 28,5,10,9,6,23,8,25,26,21,1,5,29,28,14,8,10,1,13,20]
